package interpreter;

import java.io.BufferedReader;
import java.util.Scanner;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

/*
 * Problem 10033
 * Date: 3/13/2012
 * Algorithm: Pretty Straight forward.
 */
class Main implements Runnable
{
    static String ReadLn(int maxLength) 
    {
        byte line[] = new byte[maxLength];
        int length = 0;
        int input = -1;
        try {
            while (length < maxLength) {
                input = System.in.read();
                if ((input < 0) || (input == '\n'))
                    break;
                line[length++] += input;
            }

            if ((input < 0) && (length == 0))
                return null;
            return new String(line, 0, length);
        } catch (IOException e) {
            return null;
        }
    }
    
	public static void main(String [] args)
	{
        Main myWork = new Main();
        myWork.run();
	}
	
    public void run() 
    {
    	new Interpreter().run();
    }
}

class Interpreter implements Runnable
{
	private static final int MAX_LENGTH = 1024;
	
	public void run()
	{
			int testCaseCount;
		  	ArrayList<Integer> ram = new ArrayList<Integer>();
		  
	        String line = Main.ReadLn(MAX_LENGTH);
	        line = line.trim();
	        testCaseCount = Integer.valueOf(line);
	        
	        Main.ReadLn(MAX_LENGTH); // throw a blank line
	        
	        for (int i = 0; i < testCaseCount; i++) 
	        {
	            if (i != 0) 
	            {
	                System.out.println();
	            }
	       
	            for (int j = 0; j < 1000; j++)
	            {
	            	ram.add(0);
	            }
	            
	            int address = 0;

	            String line2;
	            while ((line2 = Main.ReadLn(MAX_LENGTH)) != null) 
	            {
	                line2 = line2.trim();
	                if (line2.isEmpty()) 
	                {
	                    break;
	                }
	                
	                ram.set(address, Integer.parseInt(line2));
	                address++;
	            }
	            
	            System.out.println(evaluateInstructions(ram, address));
	        }
	        while (Main.ReadLn(MAX_LENGTH) != null); 
	}
	
	int evaluateInstructions(ArrayList<Integer> ram, int num)
	{
		// Create register.
		ArrayList<Integer> registers = createRegisters();
		
		int instructionCount = 0;
		boolean done = false;
		int i = 0;
		
		while(i < ram.size())
		{
			int instruction = ram.get(i);
			int operation = (instruction /100) % 10 ;
			int encode2ndDigit = (instruction /10) % 10;
			int encode3rdDigit = instruction % 10;
			
			switch (operation)
			{
			case 0:
				// Go to location of register d unless s contains 0.
				int registerSValue = registers.get(encode3rdDigit);
				
				if (registerSValue != 0)
				{
					i = registers.get(encode2ndDigit) - 1;
				}
			
				break;
			case 1:
				// Halt.
				done = true;
				
				break;
			case 2:
				// Set register d to n (between 0 and 9)
				registers.set(encode2ndDigit, encode3rdDigit);
			
				break;
			case 3:
				// Add n to register d.
				int d = registers.get(encode2ndDigit);
				d = convert(d + encode3rdDigit);
				
				registers.set(encode2ndDigit, d);
				
				break;
			case 4:
				// Multiply n to register d.
				int dd = registers.get(encode2ndDigit);
				dd = convert(dd * encode3rdDigit);
				
				registers.set(encode2ndDigit, dd);
				
				break;
			case 5:
				// Set register d to value of register s.
				registers.set(encode2ndDigit, registers.get(encode3rdDigit));
				break;
			case 6:
				// Add value of register s to register d.
				int s = registers.get(encode3rdDigit);
				int ddd = registers.get(encode2ndDigit);
				
				int result = convert(s + ddd);
				
				registers.set(encode2ndDigit, result);
				break;
			case 7: 
				// Multiply register d by value of register s.
				int ss = registers.get(encode3rdDigit);
				int dddd = registers.get(encode2ndDigit);
				
				int resultTwo = convert(ss * dddd);
				
				registers.set(encode2ndDigit, resultTwo);
				break;
			case 8:
				// Set register d to value in RAM whose address is in register a.
				int ramValue = ram.get(registers.get(encode3rdDigit));
				
				registers.set(encode2ndDigit, ramValue);
				break;
			case 9:
				// Set the value in RAM whose address is in register 'a' to the value of register s. 
				int sss = registers.get(encode2ndDigit);
				int pos = registers.get(encode3rdDigit);
				
				ram.set(pos, sss);
				break;
			}
			i++;
			instructionCount++;
			
			if (done == true)
				break;
		}
		
		return instructionCount;
	}
	
	ArrayList<Integer> createRegisters()
	{
		int initContent = 0;
		
		ArrayList<Integer> tempRegisters = new ArrayList<Integer>();
		
		for (int pos = 0; pos < 10; pos++ )
			tempRegisters.add(initContent);
		
		return tempRegisters;
	}
	
	int convert (int value)
	{
		value = value % 1000;
		
		return value;
	}
	
	int findHaltLoc(ArrayList<Integer> ram)
	{
		int v = 0;
		
		for (int i = 0; i < ram.size(); i++)
		{
			int t = ram.get(i);
			
			if (t == 100)
			{
				v = i;
				break;
			}
		}
		return v;
	}
}